Кривые Безье

Processing math: 100%

1.3. Кривые Безье

Далее мы изучим другую параметрическую многочеленную кривую, кривую Безье. Так как они обе используют полиномы для их координатных функций, степенная базисная и Безье формы математически эквивалентны; т.е. любая кривая, которая может быть представлена в одной, также может быть представлена в другой форме. Тем не менее, метод Безье превосходит степенную базисную форму для геометрического моделирования. Наша презентация кривых Безье, будет неформальной; для более строгого и полного ознакомления читатель должен ознакомится с другой литературой [Forr72; Bezi72, Bezi86; Gord74a; Chan81; Fari93; Yama88; Hosc93; Roge90].

Степенная базисная форма имеет следующие недостатки:

это неестественно для интерактивной разработки фигуры; коэффициенты ${a_i}$ сообщают очень мало геометрического представления о форме кривой. Кроме того, разработчик, как правило, хочет, задавать граничные условия на обоих концах кривой, а не только в начальной точке;
алгоритмы вычисления степенных базисных полиномов имеют алгебраическое, а не геометрическое выражение (например, метод Горнера);
численно, это довольно плохая функция; например, метод Гомера склонен к ошибкам округления, если коэффициенты сильно различаются по величине.

Метод Безье исправляет эти недостатки.

Кривая Безье $n$ -ой степени определяется так

$C(u)=sum_(i=0)^n B_{i,n}(u)P_i$ $0<=u<=1$ (1.7)

Базисная (смешивающая) функция, ${B_(i,n) (u)}$ , это классический Многочлен Бернштейна n-ой степени (Bern12; Lore86) заданный так

$B_{i,n}(u)={n!}/{i!(n-1)!}u^i(1-u)^{n-1}$ (1.8)

Геометрические коэффициенты этой функции, ${P_i}$ , называются контрольными точками. Обратите внимание, что в определении уравнения (1.7), требуется, чтобы $u∈[0,1]$ .

Примеры

Пример1.4	$n=1$ . Из уравнения (1.8) мы имеем $B_(0, 1) (u)=1-u$ и $B_(1, 1) (u)=u$ ; и из уравнения (1.7) получим следующую функцию $C(u)=(1-u)P_0+$ $uP_1$ . Это прямой линейный сегмент между точками $P_0$ и $P_1$ (смотри рисунок 1.9). Рисунок 1.9. Кривая Безье первой степени
Пример1.5	$n=2$ . Из уравнения (1.7) и (1.8) мы имеем $C(u)=(1-u)^2 P_0+$ $2u(1-u)P_1+u^2 P_2$ . Это параболическая дуга от $P_0$ к $P_2$ (смотри рис 1.10). Обратим внимание Полигон сформированный точками ${P_0,P_1,P_2}$ , называется управляющий полигон, приблизительно повторяет форму кривой; $P_0=C(0)$ и $P_2=C(1)$ ; Направление касательной к кривой в её концах – параллельны к $P_1-P_0$ и $P_2-P_1$ (это выведено позже); Кривая содержится в треугольнике сформированный $P_0 P_1 P_2$ . Рисунок 1.10. Кривая Безье второй степени
Пример1.6	$n=3$ . Мы имеем $C(u)=(1-u)^3 P_0+3u(1-u)^2 P_1+$ $3u^2 (1-u)P_2+u^3 P_3$ . Примеры кубических кривых Безье показаны на рис 1.11a по рис 1.11f. Обратим внимание Управляющий полигон имеет приближённую форму кривых; $P_0=C(0)$ и $P_3=C(1)$ ; Касательные в конечных точка параллельны $P_1-P_0$ и $P_3-P_2$ Свойство выпуклой оболочки: кривые вписаны в выпуклую оболочку, сформированную управляющими точками (рис 1.11c); Свойство уменьшающегося отклонения: нет прямой линии пересекающей кривую больше раз, чем пересекает управляющий полигон кривой (для кривой Безье в трёхмерном пространстве, заменить слова «прямая линия» словом «плоскость»). Это свойство кривой Безье демонстрирует, что она следует довольно близко от управляющего полигона и сильно от него не отклоняется рис 1.11f; В начале (когда $u=0$ ) кривая поворачивается в том же направлении, что и $P_0 P_1 P_2$ . Когда $u=1$ она поворачивается в направлении $P_1 P_2 P_3$ ; Петля в управляющем полигоне может соответствовать, а может и не соответствовать петле в кривой. Переходом между рис 1.11e и рис 1.11f будет кривая с пиком Рисунок 1.11a. Кривые Безье третьей степени Рисунок 1.11b. Рисунок 1.11c. Рисунок 1.11d. Рисунок 1.11e. Рисунок 1.11f.
Пример1.7	$n=6$ . Рис 1.12 демонстрирует закрытую кривую Безье шестой степени. Кривая гладкая в $C(0)(=C(1))$ потому что $P_1-P_0$ параллелен $P_6-P_5$ . Под гладкостью мы понимаем, что касательные в $u=0$ и $u=1$ имеют одинаковое направление.

Рисунок 1.12. Гладкая замкнутая кривая Безье шестой степени.

В дополнение к ранее упомянутым свойствам, кривые Безье инвариантны при обычных преобразованиях, таких как поворот, перемещение и масштабирование; то есть, преобразование применяется к кривой, путём применения к управляющему полигону. Мы рассмотрим эту концепцию, более подробно в Главе III для B-сплайнов (частным случаем которых, являются кривые Безье).

В любой схеме представления кривой (или поверхности) , выбор базисных функций определяет геометрические характеристики схемы. На рис 1.13а-г показаны базисные функции ${B_(i,n) (u)}$ для $n=1,2,3,9$ . Эти функции имеют следующие свойства:

Рисунок 1.13a. Многочлен Бернштейна для $n=1$

Рисунок 1.13b. $n=2$

Рисунок 1.13c. $n=3$

Рисунок 1.13d. $n=9$

Св.1.1	Не отрицательность: $B_(i,n) (u)≥0$ для всех $i,n$ и $0≤u≤1$ ;
Св.1.2	Разбиение единицы: $∑_(i=0)^nB_(i,n) (u)=1$ для всех $0≤u≤1$ ;
Св.1.3	$B_(0,n) (0)=B_(n,n) (1)=$ 1;
Св.1.4	$B_(i,n) (u)$ достигает ровно одного максимума на отрезке $[0,1]$ , то есть, в $u=i/n$ ;
Св.1.5	Симметрия: для любого n, множество многочленов ${B_(i,n) (u)}$ симметрична по отношению к $u=1⁄2$ ;
Св.1.6	Рекурсивное определение: $B_(i,n) (u)=(1-u) B_(i,n-1) (u)+uB_(i-1,n-1) (u)$ (смотри рис 1.14); мы определили $B_(i,n) (u)≡0$ если $i<0$ или $i>n$ ;
Рисунок 1.14. Рекурсивное определение многочлена Бернштейна, $B_{1,3}(u)$ Из уравнения (1.8) мы имеем $B_{0,0}(u)=1$ . Используя свойство 1.6, линейные и квадратичные многочлены Бернштейна $B_{0,1}(u)=(1-u)B_{0,0}(u)+uB_{-1,0}(u)=1-u$ $B_{1,1}(u)=(1-u)B_{1,0}(u)+uB_{0,0}(u)=u$ $B_{0,2}(u)=(1-u)B_{0,1}(u)+uB_{-1,1}(u)=(1-u)^2$ $B_{1,2}(u)=(1-u)B_{1,1}(u)+uB_{0,1}(u)=(1-u)u+u(1-u)=2u(1-u)$ $B_{2,2}(u)=(1-u)B_{2,1}(u)+uB_{1,1}(u)=u^2$
Св.1.7	Производные: $B_{i,n}'(u)={dB_{i,n}(u)}/{du}=n(B_{i-1,n-1}(u)-B_{i,n-1}(u))$ с $B_{-1,n-1}(u)≡B_{n,n-1}(u)≡0$ На рисунке 1.15a показано определение $B'_{2,5}$ , а на рисунке 1.15b - все функции кубической производной. Рисунок 1.15a. Производная $B'_{2,5}$ по $B_{1,4}$ и $B_{2,4}$ Рисунок 1.15b. ппроизводные четырех кубических полиномов Бернштейна $B_{0,3}^'$ ; $B_{1,3}^'$ ; $B_{2,3}^'$ ; $B_{3,3}^'$

Свойство 1.6 дает простые алгоритмы для вычисления значений многочленов Бернштейна при фиксированных значениях $u$ . Алгоритм А1.2 вычисляет значение $B_{i,n}(u)$ для фиксированного $u$ . Вычисление $B_{1,3}$ представлено в Таблице 1.1.

Таблица 1.1 Вычисление $B_{1,3}$
$0=B_{-2,0}$				$B_{-1,2}$
	↘
		$B_{-1,1}$				$B_{0,3}$
	↗		↘
$0=B_{-1,0}$				$B_{0,2}$
	↘		↗		↘
		$B_{0,1}$				$B_{1,3}$
	↗		↘		↗
$1=B_{0,0}$				$B_{1,2}$
	↘		↗
		$B_{1,1}$				$B_{2,3}$
	↗
$0=B_{1,0}$				$B_{2,2}$

Алгоритм А1.2

Bernstein(i,n,u,B)
{ /* Вычисление значения многочлена Бернштейна */
  /* Вход: i,n,u  */
  /* Выход: B */
for (j=0; j<=n; j++) /* вычисление колонок */
   temp[j] = 0.0; /* Таблицы 1.1 */
temp[n-i] = 0.0; /* во временный массив */
u1 = 1.0 – u;
for (k=0; k<=n; k++)
   for (j=0; j>=k; j++)
      temp[j] = u1*temp[j] + u*temp[j-1];
B = temp[n];
}

Алгоритм А1.3 вычисляет $n-1$ многочлена Бернштейна $n$ ой степени с ненулевым фиксированным $u$ . Это позволяет избежать ненужных вычислений нулевых условий. Алгоритм изображен в таблице 1.2 для кубического случая.

Таблица 1.2 Вычисление всех кубических многочленов Бернштейна
		$B_{-1,1}$				$B_{0,3}$
						↗
$B_{-1,0}$				$B_{0,2}$
			↗		↘
		$B_{0,1}$				$B_{1,3}$
	↗		↘		↗
$1=B_{0,0}$				$B_{0,2}$
	↘		↗		↘
		$B_{1,1}$				$B_{2,3}$
			↘		↗
$B_{1,0}$				$B_{2,2}$
					↘
		$B_{2,1}$				$B_{3,3}$

Алгоритм А1.3

AllBernstein(n,u,B)
{ /* Вычисление всех многочленов Бернштейна n-ой степени */
/* Вход: n,u  */
/* Выход: B (массив, B[0], …, B[n]) */
B[0] = 1.0;
u1 = 1.0 – u;
for (j=1; j<=n; j++)
   {
   saved = 0.0;
   for (k=0; k<j; k++)
      {
      Temp = B[k];
      B[k] = saved + u1* temp;
      saved = u*temp;
      }
   B[j] = saved
   }
}

Алгоритм А1.4 комбинирует А1.3 и уравнение (1.7) вычисляет точку на кривой Безье $n$ ой степени с фиксированным значением $u$ .

Алгоритм А1.4

PointOnBezierCurve(P,n,u,C)
{ /* Вычисление точку на кривой Безье */
  /* Вход: P,n,u  */
  /* Выход: C (точка) */
AllBernstein(n,u,B)  /* B локальный массив */
C = 0.0;
for (k=0; k<=n; k++)
   C = C + B[k]*P[k];
}

Используя свойство 1.7, легко вывести общее выражение производных кривой Безье

$C'(u)={d(sum_{i=0}^n B_{i,n}(u)P_i)}/{du}=sum_{i=0}^nB'_{i,n}(u)P_i$

$=sum_{i=0}^n n(B_{i-1,n-1}(u)-B_{i,n-1}(u))P_i$

$=nsum_{i=0}^{n-1}B_{i,n-1}(u)(P_{i+1}-P_i)$ (1.9)

Из уравнения (1.9) легко получить формулы для конечных производных кривой Безье, например

$C'(0)=n(P_1-P_0)$ $C''(0)=n(n-1)(P_0-2P_1+P_2)$

$C'(1)=n(P_n-P_{n-1})$ $C''(1)=n(n-1)(P_n-2P_{n-1}+P_{n-2})$ (1.10)

Обратите внимание, из уравнений (1.9) и (1.0) следует, что

производные кривой Безье $n$ ой степени является кривая Безье $(n-1)$ -ой степени;
выражения для конечных производных в $u=0$ и $u=1$ симметричны (из-за, конечно, симметрии базисных функций);
$k$ -ая производная в конечной точке зависит (в геометрически очень интуитивным способом) исключительно от $k+1$ контрольных точек на том конце.

Пусть $n=2$ и $C(u)=sum_{i=0}^2B_{i,2}(u)P_i$ . Тогда

$C(u)=(1-u)^2 P_0+2u(1-u)P_1+u^2 P_2$

$=(1-u)"("ubrace((1-u)P_0+uP_1)_("линеный")")"+u"("ubrace((1-u)P_1+uP_2)_("линеный")")"$

Таким образом, $C(u)$ получают в виде линейной интерполяции двух кривых Безье первой степени; В частности, любая точка на $C(u)$ получается три линейной интерполяции.

Если предположить, что $u=u_0$ фиксированно и дать $P_{1,0}=(1-u_0)P_0+u_0 P_1$ , $P_{1,1}=(1-u_0)P_1+u_0 P_2$ , и $P_{2,0}=(1-u_0)P_{1,0}+u_0 P_{1,1}$ , следует что $C(u_0)=P_{2,0}$ . Ситуация показана на рис 1.16, и кубический случай показан на рис 1.17.

Рисунок 1.16. Получение точки на квадратичной кривой Безье путем многократной линейной интерполяции при $u=2⁄5$

Рисунок 1.17. Точка на кубической кривой Безье с помощью повторной линейной интерполяции в $u=2⁄5$

Обозначая общую кривую Безье $n$ -ой степени как $C_n(P_0,...,P_n)$ , мы имеем

$C_n(P_0,...,P_n)=(1-u)C_{n-1}(P_0,...,P_{n-1})+uC_{n-1}(P_0,...,P_n)$ (1.11)

Это следует из рекурсивного определения базисных функций (смотри свойство 1.6). Фиксированное $u=u_0$ и обозначая $P_i$ как $P_{0,i}$ , уравнение (1.11) дает рекурсивный алгоритм для вычисления $C(u_0)=P_{n,0}(u_0)$ на кривой Безье $n$ -ой степени, т.е.

$P_{k,i}(u_0)=(1-u_0)P_{k-1,i}(u_0)+u_0P_{k-1,i+1}(u_0 )$ где ${(k=(1,...,n)),(i=(0,...,n-k)):}$ (1.12)

Уравнение (1.12) называются Алгоритм де Кастельжо. Это процесс отрезания углов (смотри рис 1.16 и 1.17) который даёт треугольную таблицу точек показаную в Таблице 1.3.

Алгоритм А1.5

deCasteljau1(P,n,u,C)
{ /* Вычисление точку на кривой Безье */
  /* Алгоритм де Кастельжо */
  /* Вход: P,n,u  */
  /* Выход: C (точка) */
for (i=0; i<=n; i++)  /* Используя локальный массив таким образом, мы не */
   Q[i] = P[i];       /* разрушаем контрольные точки */
for (k=0; k<=n; k++)
   for (i=0; i<=n-k; i++)
      Q[i] = (1.0 - u)*Q[i] + u*Q[i + 1];
C = Q[0];
}

Таблица 1.3 Точки генерируемые алгоритмом де Кастельжо
$P_0$
	$P_{1,0}$
$P_1$		$P_{2,0}$
	$P_{1,1}$
$P_2$		$vdots$
$vdots$	$vdots$	$vdots$		$P_{n-1,0}$
$vdots$	$vdots$	$vdots$	$cdots$		$P_{n,0}=C(u_0)$
$vdots$	$vdots$	$vdots$		$P_{n-1,1}$
$P_{n-2}$		$vdots$
	$P_{1,n-2}$
$P_{n-1}$		$P_{2,n-2}$
	$P_{1,n-1}$
$P_n$

Мы закончим этот параграф сравнением Безье и степенных базисных методов. Очевидно, что формула Безье является более геометрической из двух. Уравнение (1.10), а с выпуклой оболочкой и свойствами осцилляции делает кривые Безье более подходящими для интерактивного дизайна кривой. Контрольные точки дают разработчику более интуитивные ручки для формы кривой, чем коэффициенты степенных базисов. Кроме того, алгоритм де Кастельжо менее склонен к ошибкам округления, чем алгоритм Горнера. Это интуитивно понятно, если учесть, что алгоритм де Кастельжо просто повторяют линейную интерполяцию между точками, в каждом из которых лежат в непосредственной близости от кривой. Единственный недостаток формулы Безье является то, что оценка точки является менее эффективным (см Алгоритмы A1.1, A1.4, и A1.5, и Упражнение 1.13 позже в этой главе).